class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        def search(node):
            if not node:
                return -1001, -1001
            else:
                max_root1, max_without_roo1 = search(node.left)
                max_root2, max_without_roo2 = search(node.right)
            max_root = max(node.val, node.val + max_root1, node.val + max_root2)
            max_without_root = max(max_without_roo1, max_without_roo2, node.val + max_root1 + max_root2, max_root1, max_root2)
            return max_root, max_without_root

        max_root, max_without_root = search(root)
        return max(max_root, max_without_root)



